package com.leetcode.sort;

public class SortColors {
    public static void main(String[] args) {

    }

    public void sortColors(int[] nums) {
        int max = 2;
        int min = 0;
        int[] count = new int[max - min + 1];
        for (int num : nums) {
            count[num - min]++;
        }
        for (int i = 1; i < count.length; i++) {
            count[i] = count[i] + count[i - 1];
        }
        int[] res = new int[nums.length];
        for (int num : nums) {
            res[--count[num - min]] = num;
        }
    }

    public void sortColors2(int[] nums) {
        int ptr = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                int tmp = nums[ptr];
                nums[ptr] = nums[i];
                nums[i] = tmp;
                ptr++;
            }
        }

        for (int i = ptr; i < nums.length; i++) {
            if (nums[i] == 1) {
                int tmp = nums[ptr];
                nums[ptr] = nums[i];
                nums[i] = tmp;
                ptr++;
            }
        }
    }

    public void sortColors3(int[] nums) {
        int ptr0 = 0;
        int ptr1 = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1) {
                int tmp = nums[i];
                nums[i] = nums[ptr1];
                nums[ptr1] = tmp;
                ptr1++;
            } else if (nums[i] == 0) {
                int tmp = nums[i];
                nums[i] = nums[ptr0];
                nums[ptr0] = tmp;
                if (ptr0 < ptr1) {
                    tmp = nums[i];
                    nums[i] = nums[ptr1];
                    nums[ptr1] = tmp;
                }
                ptr0++;
                ptr1++;
            }
        }
    }
}
